package cn.lena.leecode.arr;

import org.junit.Test;

/**
 * @author lena
 * @date 2021/6/22
 * t
 */
public class Offer12 {

	@Test
	public void testOffer12(){
		//char[][] board={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
		//String word="ABCCED";
		//char[][] board={{'a'}};
		//String word="AAA";
		char[][] board={{'a','a'}};
		String word="aaa";
		System.out.println(exist(board,word));
	}

	/**
	 * 剑指offer12：矩阵中的路径
	 * @param board 矩阵
	 * @param word 单词
	 * @return
	 */
	public boolean exist(char[][] board, String word) {
		if(word.length() == 0){
			return true;
		}
		// 用于存储当前单元格使用情况
		boolean[][] use=new boolean[board.length][board[0].length];
		char[] w=word.toCharArray();
		// 表示当前遍历的是第几个元素，用于判断单元格是否使用
		int num=1;
		for(int i=0;i<board.length;i++) {
			for(int j=0;j<board[0].length;j++) {
				if(find(board,i,j,w,0,num,use)){
					return true;
				}
			}
		}
		return false;

	}

	private boolean find(char[][] board,int i,int j,char[] c,int current,int num,boolean[][] use) {
		// 匹配元素大于等于单词长度，表示全部匹配成功
		if(current == c.length) {
			return true;
		}
		// 索引越界 字符不匹配 路径已存在该节点
		if(i >= board.length || j >= board[0].length || i < 0 || j < 0 || board[i][j] != c[current] || use[i][j]) {
			return false;
		}
		// 匹配成功
		use[i][j]=true;
		num++;
		current++;
		// 遍历上下左右
		boolean result= find(board,i-1,j,c,current,num,use) || find(board,i+1,j,c,current,num,use)
				|| find(board,i,j-1,c,current,num,use) || find(board,i,j+1,c,current,num,use);
		use[i][j]=false;
		return result;
	}


}
